package day_6_27;

public class Main1 {
    /**
     * 52. N 皇后 II
     * https://leetcode.cn/problems/n-queens-ii/description/
     */
    boolean[] cheackCol;
    boolean[] cheackDig1;
    boolean[] cheackDig2;
    int ret = 0;
    int nn;

    public int totalNQueens(int n) {
        nn = n;
        cheackCol = new boolean[n];
        cheackDig1 = new boolean[n * 2];
        cheackDig2 = new boolean[n * 2];

        dfs(0); // 代表行

        return ret;
    }

    public void dfs(int row) {
        if(row == nn) {
            ret++;
        }

        for(int col = 0;col < nn;col++) {
            // cheackDig1[col - row + nn] 正常会出现负数的情况，增加偏移量，使之为正数
            if(cheackCol[col] == false && cheackDig1[col - row + nn] == false && cheackDig2[col + row] == false) {
                cheackCol[col] = cheackDig1[col - row + nn] = cheackDig2[col + row] = true;

                dfs(row + 1);

                cheackCol[col] = cheackDig1[col - row + nn] = cheackDig2[col + row] = false;
            }
        }
    }
}
